package com.example.demo.test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 锯齿形层序遍历
 * @Author wzh
 * @Date 2022/6/15 9:59 上午
 * @Version 1.0
 */
public class Lc103 {
    public static void main(String[] args) {
        TreeNode treeNode9 = new TreeNode(9,null,null);
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode6 = new TreeNode(7);
        TreeNode treeNode20 = new TreeNode(20,treeNode3,treeNode6);
        TreeNode treeNode5 = new TreeNode(3,treeNode9,treeNode20);
        System.out.println(zigzagLevelOrder(treeNode5));
    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root != null){
            deque.offer(root);
        }
        boolean isOrderLeft = true;
        while (!deque.isEmpty()){
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if(isOrderLeft){
                    levelList.offerLast(poll.val);
                }else{
                    levelList.offerFirst(poll.val);
                }
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
            ans.add(new LinkedList<>(levelList));
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }
}
